package features.advance.leetcode.tree.medium;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.ArrayList;
import java.util.List;

/**
 *  剑指 Offer 33. 二叉搜索树的后序遍历序列
 *
 *  难度：中等
 *
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，
 * 否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 * 示例 1：
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 * 示例 2：
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 *
 *
 * 提示：
 *
 * 数组长度 <= 1000
 *
 * @author LIN
 * @date 2021-06-22
 */
public class Offer33 {

    public static void main(String[] args) {
        int[] postorder = {1,3,2,6,5};

        Solution solution = new Solution() {
        };
        boolean b = solution.verifyPostorder(postorder);
        System.out.println(b);
        TreeNode root = TreeUtil.stringToTreeNode("[6,7,9,16,12,10,11]");

        solution.postorder(root);
    }

    static class Solution {
        public boolean verifyPostorder(int[] postorder) {


            return false;
        }

        /**
         * 后序遍历
         * @param root
         */
        private List<Integer> p = new ArrayList<>();
        void postorder(TreeNode root){
            if(root != null){
                postorder(root.left);
                postorder(root.right);
                System.out.println(root.val);
            }
        }
    }
}
